package com.jjlin.chapter_2;

import java.util.*;
public class CD112{
    public static class Node{
        public int val;
        public Node next;
        public Node(int data){
            this.val = data;
        }
    }

    public static Node createNodeList(int[] nums){
        Node head = new Node(nums[0]);
        Node tmp = head;
        for(int i = 1; i < nums.length; i++){
            Node newNode = new Node(nums[i]);
            tmp.next = newNode;
            tmp = newNode;
        }
        return head;
    }

    //need O(1) extra space
    public static boolean isPalindrome(Node head){
        if(head == null || head.next == null)
            return true;
        Node n1 = head;
        Node n2 = head;
        while(n2.next != null && n2.next.next != null){// find mid node
            n1 = n1.next;// n1 -> mid
            n2 = n2.next.next;// n2 -> end
        }
        n2 = n1.next; // n2 -> right part first node
        n1.next = null; // mid.next -> null
        Node n3 = null;
        while(n2 != null){ // right part convert
            n3 = n2.next; // n3 -> save next node
            n2.next = n1; // next of right node convert
            n1 = n2; // n1 move
            n2 = n3; // n2 move
        }
        n3 = n1; // n3 -> save last node
        n2 = head; // n2 -> left first node
        while(n1 != null && n2 != null){
            if(n1.val != n2.val) // check palindrome
                return false;
            n1 = n1.next; // left to mid
            n2 = n2.next; // right to mid
        }
        n2 = n3.next;
        n3.next = null;//别忘了将最后一个结点的next置空
        while(n2 != null){// recover list
            n1 = n2.next;
            n2.next = n3;
            n3 = n2;
            n2 = n1;
        }
        return true;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int[] nums = new int[len];
        for(int i = 0; i < len; i++)
            nums[i] = sc.nextInt();
        Node head = createNodeList(nums);
        System.out.println(isPalindrome(head));
    }
}
